package com.leetcode;

import com.leetcode.common.ListNode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

import static com.leetcode.util.LinkedListUtil.createList;
import static com.leetcode.util.LinkedListUtil.printList;

/**
 * 445. 两数相加 II
 * 三个堆栈 操作加法
 */
public class Solution445 {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> stack1 = new ArrayDeque<>();
        Deque<Integer> stack2 = new ArrayDeque<>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        int carry = 0;
        ListNode res = null;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int num1 = stack1.isEmpty() ? 0 : stack1.pop();
            int num2 = stack2.isEmpty() ? 0 : stack2.pop();
            int val = num1 + num2 + carry;

            carry = val / 10;
            val = val % 10;

            ListNode node = new ListNode(val);
            node.next = res;
            res = node;
        }
        return res;
    }

    public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        Stack<Integer> stack = new Stack<>();
        int carry = 0;
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            int val = carry;
            if (!stack1.isEmpty()) {
                val += stack1.pop();
            }
            if (!stack2.isEmpty()) {
                val += stack2.pop();
            }
            carry = val / 10;
            val = val % 10;
            stack.push(val);
        }
        if (carry > 0) {
            stack.push(carry);
        }
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while (!stack.isEmpty()) {
            cur.next = new ListNode(stack.pop());
            cur = cur.next;
        }
        return dummyHead.next;
    }

    public static void main(String[] args) {
        ListNode l1 = createList(new int[]{0});
        ListNode l2 = createList(new int[]{0});

        ListNode head = new Solution445().addTwoNumbers(l1, l2);
        printList(head);
    }

}
